/*
题目: 相似度为 k 的字符串
对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。

给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。

https://leetcode.cn/problems/k-similar-strings
 */
public class KSimilarity {
    int n ;

    public static class Pair {
        public String str;
        public int pos ;
        public Pair(String str, int pos) {
            this.str = str;
            this.pos = pos;
        }
    }

    public int kSimilarity(String exp, String tar) {
        // 广度优先
        n = exp.length();
        Set<String> visited = new HashSet<> (); // 防止多次访问
        Queue<Pair> queue = new LinkedList<> ();

        // Pair 表示 字符串 Str 到 i 下标为止 和 tar 不一样
        queue.offer(new Pair(exp, 0));
        visited.add(exp);

        int k = 0;
        while (! queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Pair cur = queue.poll();
                if (cur.str.equals(tar))    return k;

                int i = cur.pos; // POS 位置是第一个不相等的 下标
                while (i < n && cur.str.charAt(i) == tar.charAt(i)) {
                    i ++;
                }

                for (int j = i + 1; j < n; j ++) {
                    // 满足条件可以交换, 并且 可以 省一步交换, 相同位置相同字符 不用动
                    if (cur.str.charAt(j) == tar.charAt(i) && cur.str.charAt(j) != tar.charAt(j)) {
                        String next = swap(cur.str, j, i);
                        if (visited.add(next)) {
                            queue.offer(new Pair(next, i + 1));
                        }
                    }
                }
            }

            k ++;
        }

        return k;
    }

    private String swap(String exp, int a, int b) {
        char[] cs = exp.toCharArray();
        char t = cs[a];
        cs[a] = cs[b];
        cs[b] = t;
        return new String(cs);
    }
}
